{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 跳跃游戏【中等】"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "跳跃游戏\n",
    "\n",
    "给定一个非负整数数组，你最初位于数组的第一个位置。\n",
    "\n",
    "数组中的每个元素代表你在该位置可以跳跃的最大长度。\n",
    "\n",
    "判断你是否能够到达最后一个位置。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: [2,3,1,1,4]\n",
    "\n",
    "输出: true\n",
    "\n",
    "解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: [3,2,1,0,4]\n",
    "\n",
    "输出: false\n",
    "\n",
    "解释: 无论怎样，你总会到达索引为 3 的位置。\n",
    "\n",
    "但该位置的最大跳跃长度是0，所以你永远不可能到达最后一个位置。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#==============================答题区==============================#\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#==============================答题区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#==============================提示区==============================#\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#  提示：贪心算法，每次跳时选择index+value最大的位置，如果遇到了0则说明跳不出来。\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#==============================提示区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#==============================答案区==============================#\n",
    "# 解题思路1：存在某个0，且这个0前面的每个数的大小都小于等于它和0之间的距离，则说明跳不出来\n",
    "\n",
    "def f(arr):\n",
    "    zeros_idx = [i for i,x in enumerate(arr) if x==0]\n",
    "    for z in zeros_idx:\n",
    "        if all([arr[i]<= z-i for i in range(0,z)]):\n",
    "            return(False)\n",
    "    return(True)\n",
    "\n",
    "print(f([1,2,3]))\n",
    "print(f([3,2,1,0,1]))\n",
    "print(f([4,2,0,2,0,1]))\n",
    "#==============================答案区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#==============================答案区==============================#\n",
    "# 解题思路2：贪心算法\n",
    "# 每次跳时选择index+value最大的位置，如果遇到了0则说明跳不出来了\n",
    "# 每个位置i能往前跳的步数<=arr[i]\n",
    "\n",
    "def f(arr):\n",
    "    i = 0\n",
    "    while i<len(arr)-1:\n",
    "        if arr[i]==0:\n",
    "            return(False)\n",
    "        reachables = range(i+1,min(i+arr[i]+1,len(arr)))  \n",
    "        i = sorted(reachables,key = lambda k: k+arr[k],reverse = True)[0]\n",
    "    if i>=len(arr)-1:\n",
    "        return(True)\n",
    "print(f([1,2,3]))\n",
    "print(f([3,2,1,0,1]))\n",
    "print(f([4,2,0,2,0,1]))\n",
    "#==============================答案区==============================#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](../Python与算法之美.jpg)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
